package com.autumn.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 斐波那契数列
 * 0，1，1，2，3，5……，第3项开始，每一项都等于前两项之和
 */
public class Algorithm02Fibonacci {
    /**
     * 解法一：递归
     *
     * @param n
     * @return
     */
    public static int fibonacciByRecursive(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacciByRecursive(n - 1) + fibonacciByRecursive(n - 2);
    }

    private static Map<Integer, Integer> storeMap = new HashMap<>();

    /**
     * 解法二：递归 + HashMap存储中间计算结果
     *
     * @param n
     * @return
     */
    public static int fibonacciByRecursiveAndMap(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (null != storeMap.get(n)) {
            return storeMap.get(n);
        } else {
            int result = fibonacciByRecursiveAndMap(n - 1) + fibonacciByRecursiveAndMap(n - 2);
            storeMap.put(n, result);
            return result;
        }
    }

    /**
     * 解法三：for循环：自底向上累加
     *
     * @param n
     * @return
     */
    public static int fibonacciByFor(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int result = 0;
        int pre = 1;
        int prePre = 0;
        for (int i = 1; i < n; i++) {
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 25;

        long start1 = System.currentTimeMillis();
        int num1 = fibonacciByRecursive(n);
        long end1 = System.currentTimeMillis();
        System.out.println("第" + n + "个数为：" + num1 + "，递归耗时：" + (end1 - start1));

        long start2 = System.currentTimeMillis();
        int num2 = fibonacciByRecursiveAndMap(n);
        long end2 = System.currentTimeMillis();
        System.out.println("第" + n + "个数为：" + num2 + "，递归加Map耗时：" + (end2 - start2));

        long start3 = System.currentTimeMillis();
        int num3 = fibonacciByFor(n);
        long end3 = System.currentTimeMillis();
        System.out.println("第" + n + "个数为：" + num3 + "，for循环耗时：" + (end3 - start3));
    }

}
